package com.wfm.leetcode.editor.cn;

import com.wfm.alg.P树状数组;
import org.junit.Test;
import sun.awt.geom.AreaOp.SubOp;

/**
 * 线段树，用数组保存的解法
 * 实际上就是带着参数去左子区间找或者右子区间找的意思。
 * 比如：查找区间[left，right]的和，判断right是不是小于m，如果是代表求和的区间在左子树，
 *      如果left>m,代表求和的区间在右子树，于是是右子树找
 *      否则，说明求和区间跨两颗子树，于是一部分[left，m]去左子树找，[m,right]去右子树找
 * 更新也是一样的，根据更新的index在左或右，去找，然后再自底向上更新树的节点的值。
 *
 * 时间复杂度：
 * 构造函数：O(n)
 * update O(logn)
 * sumRange O(logn)
 *
 * 空间复杂度：O(n)
 *
 */
public class PThree07区域和检索数组可修改{
//leetcode submit region begin(Prohibit modification and deletion)
class NumArray {

    public NumArray(int[] nums) {
        N = nums.length - 1;
        for (int i = 0; i <= N; i++) {
            update(root, 0, N, i, i, nums[i]);
        }
    }

    public void update(int index, int val) {
        update(root, 0, N, index, index, val);
    }

    public int sumRange(int left, int right) {
        return query(root, 0, N, left, right);
    }

    class Node {
        // 左右孩子节点
        Node left, right;
        // 当前节点值，以及懒惰标记的值
        int val, add;
    }
    private int N;
    private Node root = new Node();
    public void update(Node node, int start, int end, int l, int r, int val) {
        if (l <= start && end <= r) {
            node.val = (end - start + 1) * val;
            node.add = val;
            return ;
        }
        int mid = (start + end) >> 1;
        pushDown(node, mid - start + 1, end - mid);
        if (l <= mid) update(node.left, start, mid, l, r, val);
        if (r > mid) update(node.right, mid + 1, end, l, r, val);
        pushUp(node);
    }
    public int query(Node node, int start, int end, int l, int r) {
        if (l <= start && end <= r) return node.val;
        int mid = (start + end) >> 1, ans = 0;
        pushDown(node, mid - start + 1, end - mid);
        if (l <= mid) ans += query(node.left, start, mid, l, r);
        if (r > mid) ans += query(node.right, mid + 1, end, l, r);
        return ans;
    }
    private void pushUp(Node node) {
        node.val = node.left.val + node.right.val;
    }
    private void pushDown(Node node, int leftNum, int rightNum) {
        if (node.left == null) node.left = new Node();
        if (node.right == null) node.right = new Node();
        if (node.add == 0) return ;
        node.left.val = node.add * leftNum;
        node.right.val = node.add * rightNum;
        node.left.add = node.add;
        node.right.add = node.add;
        node.add = 0;
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(index,val);
 * int param_2 = obj.sumRange(left,right);
 */
//leetcode submit region end(Prohibit modification and deletion)


//class NumArray {
//
//    int[] segmentTree;
//    int n;
//    public NumArray(int[] nums) {
//        n=nums.length;
//        segmentTree=new int[n*4];
//        buildTree(0,0,n-1,nums);
//    }
//
//    public void update(int index, int val) {
//        set(index,val,0,0,n-1);
//    }
//
//    public int sumRange(int left, int right) {
//        return range(left,right,0,0,n-1);
//    }
//    // 以node为根节点，以s为左区间，e为右区间，建立线段树
//    private void buildTree(int node,int s,int e,int[] nums){
//        if(s==e){
//            segmentTree[node]=nums[s];
//            return;
//        }
//        int m = s+(e-s)/2;
//        buildTree(node*2+1,s,m,nums);//建立node的左孩子树
//        buildTree(node*2+2,m+1,e,nums);// 建立node的右孩子树
//        segmentTree[node]=segmentTree[node*2+1]+segmentTree[node*2+2];
//    }
//    // 在以node为节点，区间为[s,e]的线段树里设置index下标值变成val
//    private void set(int index,int val,int node,int s,int e){
//        if(s==e){
//            segmentTree[node]=val;
//            return;
//        }
//        int m = s+(e-s)/2;
//        if(index<=m){
//            set(index,val,node*2+1,s,m);
//        }else {
//            set(index,val,node*2+2,m+1,e);
//        }
//        segmentTree[node]=segmentTree[node*2+1]+segmentTree[node*2+2];
//    }
//
//    // 以nod为节点，区间为[s,e]的树下，累加区间为[left，right]的和
//    private int range(int left,int right,int node,int s,int e){
//        if(left==s&&right==e){
//            return segmentTree[node];
//        }
//        int m = s+(e-s)/2;
//        if(right<=m){
//            return range(left,right,node*2+1,s,m);
//        }else if(left>m){
//            return range(left,right,node*2+2,m+1,e);
//        }else{
//            return range(left,m,node*2+1,s,m)+range(m+1,right,node*2+2,m+1,e);
//        }
//    }
//}


    public static void main(String[] args) {
        NumArray solution = new PThree07区域和检索数组可修改().new NumArray(new int[]{0,1,2,3,4});
        // 10,6,10,2
        System.out.println(solution.sumRange(0, 4));
        System.out.println(solution.sumRange(1, 3));
        System.out.println(solution.sumRange(1, 4));
        System.out.println(solution.sumRange(2, 2));
        solution.update(2,5);
        // 13，9,13，5
        System.out.println(solution.sumRange(0, 4));
        System.out.println(solution.sumRange(1, 3));
        System.out.println(solution.sumRange(1, 4));
        System.out.println(solution.sumRange(2, 2));
        //=====================================

    }


//=====================树状数组======================
    class NumArray1 {
        P树状数组 numTree;
        int _nums[];
        public NumArray1(int[] nums) {
             numTree = new P树状数组(nums);
             _nums = nums;
        }

        public void update(int index, int val) {
            numTree.add(index+1,-_nums[index]+val);
        }

        public int sumRange(int left, int right) {
            int L = numTree.query(left-1+1);// 减一是因为比如我求1~2，1要算在内，所以left只能到0，加一是因为树状数组从1开始
            int R = numTree.query(right+1);
            return R-L;
        }

    }
    @Test
    public void test2(){
        int[] ints = {1,2,3,4,5,6,7,8};
        NumArray1 numArray1 = new NumArray1(ints);
        System.out.println(numArray1.sumRange(0, ints.length-1));
        numArray1.update(1,5);
        System.out.println(numArray1.sumRange(0, ints.length-1));
        System.out.println(numArray1.sumRange(1, 2));
    }
}